/*
Problem:
Assemble:
Anthor:     Alchemist
Date:
Tag:
Difficulty:
Description:
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int maxn = 1000000 +1;
int al[maxn] = {0};
int n,q;

struct node
{
    int l,r,m;
    node *left,*right;
};

node* root;

void build(int l, int r, node* root)
{
    if(l < r)
    {
        root->left = new node();
        root->right = new node();
        build(l, (l+r)/2, root->left);
        build((l+r)/2 + 1, r, root->right);
        root->l = l;
        root->r = r;
        root->m = max(root->left->m, root->right->m);
    }
    else if(l == r)
    {
        root->l = l;
        root->r = r;
        root->m = al[l];
    }
}

int search(int l, int r, node* root)
{
    int x, y;
    x = 0xffffffff;
    y = 0xffffffff;
    //cout << l << ' ' << r << ' ' << root->l << ' ' << root->r << endl;
    if(l == root->l && r == root->r)
    {
        return root->m;
    }
    if(l <= root->left->r)
    {
        x = search(l, min(root->left->r,r), root->left);
    }
    if(root->right->l <= r)
    {
        y = search(max(root->right->l,l), r, root->right);
    }
    return max(x,y);
}

void init()
{
    cin >> n;
    for(int i = 0; i <= n ; i ++)
    {
        scanf("%d", &al[i]);
    }
    root = new node();
    build(0,n,root);
    cin >> q;
}

int main()
{
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    init();
    int a,b;
    for(int i = 0; i < q; i ++)
    {
        scanf("%d%d",&a,&b);
        cout << search(a,b,root) << endl;
    }
    return 0;
}
